package com.leetcode.www;

import java.util.Arrays;

/**
 * Creared with IntelliJ IDEA.
 * Description:给你一个长度为 n 的整数数组nums和 一个目标值target。请你从 nums 中选出三个整数，使它们的和与target最接近。
 *
 * 返回这三个数的和。
 *
 * 假定每组输入只存在恰好一个解。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/3sum-closest
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * User:yxd
 * Date:2022-03-22
 * Time:22:26
 */
public class Array16 {
    public int threeSumClosest(int[] nums, int target) {
        //能不能先将数组进行整体排序,看一下目标值大概位于哪里,在目标值的两边进行选择
        Arrays.sort(nums);
        int maxc = 1000;//最大限制是1000
        for(int i = 0;i < nums.length;i ++){
            if(i > 0 && nums[i] == nums[i - 1]){
                continue;
            }
            int s = i + 1;
            int e = nums.length - 1;
            while(s < e){
                int sum = nums[i] + nums[s] + nums[e];
                if(sum == target){//如果直接等于就退出
                    return sum;
                }
                if(Math.abs(target - sum) < Math.abs(maxc - target)){
                    maxc = sum;
                }
                if(sum > target){
                    while(s < e && nums[e] == nums[--e]);
                }else{
                    while(s < e && nums[s] == nums[++s]);
                }
            }
        }
        return maxc;
    }
    public int threeSumClosest2(int[] nums, int target) {
        //直接暴力
        int count = 1000;
        for(int i = 0;i < nums.length - 2;i ++){
            for(int j = i + 1;j < nums.length- 1;j ++){
                for(int z = j + 1;z < nums.length;z ++){
                    int sum = nums[i] + nums[j] + nums[z];
                    if(sum == target){
                        return sum;
                    }
                    if(Math.abs(sum - target) < Math.abs(count - target)){
                        count = sum;
                    }
                }
            }
        }
        return count;
    }
}
